package gsw.tool.datastructure.table;

import gsw.tool.common.ToolShow;

/**
 * 单链表
 *
 * @param <E>
 */
public class LinkedTable<E> {
    //首节点
    Node<E> first;
    //链表大小
    int size;

    public static void test() {
        LinkedTable<String> linkedTable = new LinkedTable<String>();
        String s1 = "A";
        String s2 = "B";
        String s3 = "C";
        String s4 = "D";
        linkedTable.add(0, s1);
        linkedTable.add(0, s2);
        linkedTable.add(1, s3);
        linkedTable.add(2, s4);
        ToolShow.log(linkedTable.toString());
        ToolShow.log("--------------------------");

        linkedTable.reset();
        ToolShow.log(linkedTable.toString());
        ToolShow.log("--------------------------");
    }

    /**
     * 获取元素
     *
     * @param index
     * @return
     */
    public E get(int index) {
        Node<E> node = node(index);
        E e = node == null ? null : node.item;
        return e;
    }

    /**
     * 获取节点
     *
     * @param index
     * @return
     */
    protected Node<E> node(int index) {
        if (index < 0 || index >= size) {
            return null;
        }
        Node<E> result = first;
        for (int i = 1; i <= index; i++) {
            result = result.next;
        }
        return result;
    }


    /**
     * 尾部添加元素
     *
     * @param e
     */
    public boolean add(E e) {
        return add(size, e);
    }

    /**
     * 指定位置添加元素
     *
     * @param index 添加的位置
     * @param e     添加的元素
     */
    public boolean add(int index, E e) {
        if (index < 0 || index > size) {
            return false;
        }
        //当前位置的上一个节点
        Node<E> prevNode = node(index - 1);
        //当前位置的节点
        Node<E> nowNode = prevNode == null ? node(index) : prevNode.next;
        //生成要添加的节点
        Node<E> newNode = new Node<>(e, nowNode);
        //改变新节点的指针
        if (prevNode != null) {
            prevNode.next = newNode;
        } else {
            first = newNode;
        }
        //单链表的大小
        size++;
        return true;
    }

    /**
     * 删除元素：根据对象
     *
     * @param e
     */
    public boolean remove(E e) {
        Node<E> preNode = null;
        Node<E> nowNode = first;
        while (nowNode != null) {
            if (nowNode.item == e) {
                return removeByPre(preNode);
            } else {
                preNode = nowNode;
                nowNode = nowNode.next;
            }
        }
        return false;
    }

    /**
     * 删除指定位置的元素
     *
     * @param index 指定的位置
     */
    public boolean remove(int index) {
        if (index < 0 || index >= size) {
            return false;
        }
        //当前位置的上一个节点
        Node<E> prevNode = node(index - 1);
        return removeByPre(prevNode);
    }

    /**
     * 根据上一个节点删除当前节点
     *
     * @param preNode 上一个节点
     */
    public boolean removeByPre(Node<E> preNode) {
        if (preNode == null) {
            first = first.next;
        } else {
            preNode.next = preNode.next.next;
        }
        size--;
        return true;
    }

    /**
     * 循环倒序
     */
    private boolean reset() {
        Node<E> curr = first;
        Node<E> last = null;

        while (curr != null) {
            Node<E> temp = curr.next;
            curr.next = last;
            last = curr;
            curr = temp;
        }
        first = last;
        return true;
    }

    /**
     * 递归倒序
     *
     * @param curr
     */
    private boolean reset(Node<E> curr) {
        //结束条件
        if (curr == null || curr.next == null) {
            return false;
        }
        //循环条件
        reset(curr.next);
        //循环内容
        curr.next.next = curr;
        curr.next = null;
        return true;
    }

    @Override
    public String toString() {
        StringBuffer stringBuffer = new StringBuffer();
        Node<E> nowNode = first;
        while (nowNode != null) {
            stringBuffer.append(nowNode.toString() + ",");
            nowNode = nowNode.next;
        }
        return stringBuffer.toString();
    }

    /**
     * 自定义节点
     *
     * @param <E>
     */
    public static class Node<E> {
        E item;
        Node<E> pre;
        Node<E> next;

        public Node(E item, Node<E> next) {
            this.item = item;
            this.next = next;
        }

        public Node(E item, Node<E> prev, Node<E> next) {
            this.item = item;
            this.pre = prev;
            this.next = next;
        }

        @Override
        public String toString() {
            String s = "Node{" + "item=" + item;
            if (pre != null) {
                s += ", pre=" + pre.item;
            }
            if (next != null) {
                s += ", next=" + next.item;
            }
            s += "}";
            return s;
        }
    }
}


